package com.yayako.struc;

import com.sun.istack.internal.Nullable;
import com.yayako.utils.FileUtil;

import java.util.*;
import java.util.concurrent.CopyOnWriteArrayList;

/**
 * 文法实体类（无二义性的上下文无关文法）
 *
 * @author cyy
 */
public class CFG {
    private static final String EPSILON = "ε";
    private static final String OUTPUT_PATH =
            "D:\\Projects\\Fundamentals of Compiling\\SyntacticParser\\src\\com\\yayako\\out\\cfg";
    /** 非终结符 */
    private TreeSet<String> N;
    /** 终结符 */
    private TreeSet<String> T;
    /** 文法开始符号 */
    private String S;
    /** 产生式 */
    private TreeMap<String, List<Production>> P;

    public CFG(List<String> strings) {
        creCFG(strings);
        eliminateLeftRecursion();
        extractLeftFactor();
        FileUtil.write2Txt(OUTPUT_PATH, this.toString(), false);
    }

    /**
     * 构建 CFG 数据结构
     *
     * @param strings 读入流
     */
    private void creCFG(List<String> strings) {
        N = new TreeSet<>(Arrays.asList(strings.get(0).split(" ")));
        T = new TreeSet<>(Arrays.asList(strings.get(1).split(" ")));
        T.add(EPSILON);
        S = strings.get(2);
        P = new TreeMap<>();
        List<Production> tmp;
        for (int i = 3; i < strings.size(); ++i) {
            String production = strings.get(i);
            String[] str = production.split("→");
            String left = str[0].trim();
            tmp = P.get(left);
            if (tmp == null) {
                tmp = new ArrayList<>();
            }
            for (String s : str[1].split("\\|")) {
                tmp.add(new Production(str[0], s));
            }
            P.put(left, tmp);
        }
    }

    /** 消除左递归 */
    private void eliminateLeftRecursion() {
        HashSet<String> isVisited = new HashSet<>();
        eliminateIndirectlyLeftRecursion(S, S);
        isVisited.add(S);
        while (true) {
            try {
                for (String n : N) {
                    if (isVisited.contains(n)) {
                        continue;
                    }
                    eliminateIndirectlyLeftRecursion(n, n);
                    eliminateDirectlyLeftRecursion(n);
                    isVisited.add(n);
                }
                break;
            } catch (ConcurrentModificationException ignored) {
            }
        }
    }

    /**
     * 消除间接左递归
     *
     * @param cur 当前非终结符
     * @param tar 左递归目标
     */
    private void eliminateIndirectlyLeftRecursion(String cur, String tar) {
        List<Production> productions = P.get(cur);
        // 写入复制，防止 ConcurrentModificationException
        CopyOnWriteArrayList<Production> tmp = new CopyOnWriteArrayList<>(productions);
        for (Production production : tmp) {
            String first = production.right.get(0);
            // 非直接左递归 && 不相等 && 非终结符 => 寻找间接左递归
            if (!cur.equals(first) && !first.equals(tar) && N.contains(first)) {
                eliminateIndirectlyLeftRecursion(first, tar);
            } else if (!cur.equals(first) && first.equals(tar)) {
                // 消除间接左递归
                replaceForIndirectlyLeftRecursion(tar, production);
            }
        }
    }

    /**
     * 消除直接左递归
     *
     * @param tar 左递归目标
     */
    private void eliminateDirectlyLeftRecursion(String tar) {
        List<Production> productions = P.get(tar);
        List<Production> alpha = new ArrayList<>();
        List<Production> beta = new ArrayList<>();
        // 遍历产生式，对alpha、beta分组
        for (Production production : productions) {
            String first = production.right.get(0);
            if (first.equals(tar)) {
                alpha.add(production);
            } else {
                beta.add(production);
            }
        }
        if (alpha.size() > 0) {
            // 新非终结符
            String ns = tar + "'";
            Production np = new Production(null, ns);
            N.add(ns);
            // 合并β
            productions.clear();
            replaceForDirectlyLeftRecursion(tar, productions, beta, np, -1);
            // 合并α
            List<Production> list = new ArrayList<>();
            replaceForDirectlyLeftRecursion(ns, list, alpha, np, 1);
            list.add(new Production(ns, EPSILON));
            // 更新产生式集合
            P.put(ns, list);
        }
    }

    /**
     * 直接左递归的产生式替换
     *
     * @param left 左部
     * @param tarProductions 目标产生式
     * @param beta β列表
     * @param np 新非终结符
     * @param type 合并类型
     */
    private void replaceForDirectlyLeftRecursion(
            String left,
            List<Production> tarProductions,
            List<Production> beta,
            Production np,
            int type) {
        for (Production production : beta) {
            Production p = new Production(left, production, np, type);
            tarProductions.add(p);
        }
    }

    /**
     * 间接左递归的产生式替换
     *
     * @param src 源产生式
     * @param tar 目标产生式
     */
    private void replaceForIndirectlyLeftRecursion(String src, Production tar) {
        List<Production> srcProductions = P.get(src);
        List<Production> tarProductions = P.get(tar.left);
        for (Production srcProduction : srcProductions) {
            Production p = new Production(tar.left, srcProduction, tar, 0);
            tarProductions.add(p);
        }
        tarProductions.remove(tar);
    }

    TreeSet<String> getN() {
        return N;
    }

    /** 提取左因子 */
    private void extractLeftFactor() {
        HashSet<String> isVisited = new HashSet<>();
        while (true) {
            try {
                // 遍历各非终结符的产生式
                for (String s : P.keySet()) {
                    if (isVisited.contains(s)) {
                        continue;
                    }
                    longestCommonPrefix(s, P.get(s));
                    isVisited.add(s);
                }
                break;
            } catch (ConcurrentModificationException ignored) {
            }
        }
    }

    /**
     * 寻找最长公共前缀（全篇最鸡肋代码）
     *
     * <p>依次以各产生式为前缀进行寻找，若其不为邻近下一个产生式的前缀（已经进行排序，故相同前缀的产生式必定相邻），移除其末状态再进行匹配。
     * 若经过几次while再度匹配不上，并且该前缀长度超出当前最大前缀长度，更新最长前缀及其对应产生式。每轮循环后进行一次替换。
     *
     * @param left 左部
     * @param productions 产生式
     */
    private void longestCommonPrefix(String left, List<Production> productions) {
        // 排序方便查找
        Collections.sort(productions);
        // 公共前缀所对应下标
        int index = 0;
        // 当前前缀
        String curPrefix = "";
        // 最长前缀
        String longestPrefix = "";
        // 当前包含公共前缀的产生式
        List<Production> curProds = new ArrayList<>();
        // 包含最长公共前缀的产生式
        List<Production> longestProds = new ArrayList<>();
        // 当前前缀产生式
        Production curPrefixProd = null;
        // 最长前缀产生式
        Production longestProd = null;
        while (true) {
            for (int i = 0; i < productions.size(); i++) {
                // 取首产生式右部为最初的前缀并进行比较
                if (i == 0) {
                    index = 0;
                    curPrefixProd = (Production) productions.get(0).clone();
                    curPrefix = curPrefixProd.production;
                    curProds.add(productions.get(0));
                    continue;
                }
                while (productions.get(i).production.indexOf(curPrefix) != 0) {
                    if (curProds.size() > 1) {
                        if (curPrefix.length() > longestPrefix.length()) {
                            longestProds = new ArrayList<>(curProds);
                            longestPrefix = curPrefix;
                            longestProd = (Production) curPrefixProd.clone();
                        }
                        curProds.clear();
                        curPrefixProd = (Production) productions.get(++index).clone();
                        curPrefix = curPrefixProd.production;
                        i = index;
                        break;
                    }

                    // 移除末尾的状态
                    curPrefixProd.removeLastSymbol();
                    curPrefix = curPrefixProd.production;

                    // 如果为空，换下一个产生式找前缀
                    if (curPrefix.isEmpty()) {
                        curProds.clear();
                        curPrefixProd = (Production) productions.get(++index).clone();
                        curPrefix = curPrefixProd.production;
                        i = index;
                        break;
                    }
                }
                curProds.add(productions.get(i));
            }
            if (curProds.size() > 1) {
                if (curPrefix.length() > longestPrefix.length()) {
                    longestProds = new ArrayList<>(curProds);
                    longestProd = curPrefixProd;
                }
            }
            if (longestProds.size() > 0) {
                mergeProductions(left, longestProds, longestProd, productions);
                Collections.sort(productions);
                curProds.clear();
                longestProds.clear();
                index = 0;
                longestPrefix = "";
                continue;
            }
            break;
        }
    }

    /**
     * 合并表达式
     *
     * @param left 左部
     * @param longestProds 包含最长公共前缀的产生式
     * @param prefix 最长公共前缀对应的表达式
     * @param srcProductions 原产生式列表
     */
    private void mergeProductions(
            String left,
            List<Production> longestProds,
            Production prefix,
            List<Production> srcProductions) {
        // 公共前缀代表的符号个数，也即非公共前缀符对应下标
        int index = prefix.right.size();
        // 记录非公共后缀
        List<List<String>> suffix = new ArrayList<>();
        for (Production production : longestProds) {
            suffix.add(production.right.subList(index, production.right.size()));
            srcProductions.remove(production);
        }
        // 新非终结符
        String ns = left + "'";
        while (N.contains(ns)) {
            ns = ns + "'";
        }
        N.add(ns);
        // 公共前缀符号
        List<String> tmp = new ArrayList<>(prefix.right);
        tmp.add(ns);
        srcProductions.add(new Production(left, tmp, prefix.production + ns));

        // 新产生式
        List<Production> suffixProductions = new ArrayList<>();
        for (List<String> suffixProduction : suffix) {
            suffixProductions.add(
                    new Production(ns, suffixProduction, list2String(suffixProduction)));
        }
        P.put(ns, suffixProductions);
    }

    private String list2String(List<String> list) {
        if (list.size() == 0) {
            return EPSILON;
        }
        StringBuilder res = new StringBuilder();
        for (String s : list) {
            res.append(s);
        }
        return res.toString();
    }

    TreeMap<String, List<Production>> getP() {
        return P;
    }

    public TreeSet<String> getT() {
        return T;
    }

    @Override
    public String toString() {
        T.remove(EPSILON);
        StringBuilder res =
                new StringBuilder(
                        "CFG:\n\tN = " + N + ",\n\tT = " + T + ",\n\tS = " + S + ", \n\tP:\n");
        T.add(EPSILON);
        for (Production production : P.get(S)) {
            res.append('\t').append(production).append('\n');
        }
        for (String s : P.keySet()) {
            if (s.equals(S)) {
                continue;
            }
            List<Production> list = P.get(s);
            for (Production production : list) {
                res.append('\t').append(production).append('\n');
            }
        }
        return res.toString();
    }

    String getS() {
        return S;
    }

    public static class Production implements Comparable<Production>, Cloneable {
        private String production;
        private String left;
        private List<String> right;
        private String first;

        Production(@Nullable String left, String right) {
            this.production = right.replace(" ", "");
            if (left != null) {
                this.left = left.trim();
            }
            this.right = Arrays.asList(right.trim().split(" "));
            this.first = this.right.get(0);
        }

        /**
         * 消除间接左递归，合并两个产生式
         *
         * @param src 源产生式
         * @param tar 目标产生式
         */
        Production(String left, Production src, Production tar, int type) {
            this.left = left;
            switch (type) {
                case 0:
                    this.production = src.production + tar.production.substring(1);
                    this.right = new ArrayList<>(src.right);
                    this.right.addAll(tar.right.subList(1, tar.right.size()));
                    break;
                case 1:
                    this.production = src.production.substring(1) + tar.production;
                    this.right = new ArrayList<>(src.right.subList(1, src.right.size()));
                    this.right.addAll(tar.right);
                    break;
                default:
                    if (EPSILON.equals(src.production)) {
                        this.production = tar.production;
                        this.right = new ArrayList<>(tar.right);
                    } else {
                        this.production = src.production + tar.production;
                        this.right = new ArrayList<>(src.right);
                        this.right.addAll(tar.right);
                    }
                    break;
            }
            this.first = this.right.get(0);
        }

        Production(String left, List<String> subList, String production) {
            this.left = left;
            this.production = production;
            this.right = subList;
            if (production.equals(EPSILON)) {
                this.first = EPSILON;
            } else {
                this.first = this.right.get(0);
            }
        }

        @Override
        protected Object clone() {
            Production p = null;
            try {
                p = (Production) super.clone();
                p.right = new ArrayList<>(p.right);
            } catch (CloneNotSupportedException e) {
                e.printStackTrace();
            }
            return p;
        }

        @Override
        public String toString() {
            return "\t" + left + "\t→\t" + production;
        }

        @Override
        public int compareTo(Production o) {
            if (production.indexOf(o.production) == 0) {
                return -production.length() + o.production.length();
            }
            return production.compareTo(o.production);
        }

        String getFirst() {
            return first;
        }

        public String getProduction() {
            return production;
        }

        String getLeft() {
            return left;
        }

        public List<String> getRight() {
            return right;
        }

        void removeLastSymbol() {
            String s = right.remove(right.size() - 1);
            production = production.substring(0, production.length() - s.length());
        }
    }
}
